package com.Sep_Twenty;

import java.util.ArrayList;
import java.util.List;

/**
 * 1382. 将二叉搜索树变平衡
 * 给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。
 *
 * 如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/balance-a-binary-search-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/09/20 12:07
 */

public class Solution1382 {

    List<Integer> res=new ArrayList<>();

    public TreeNode balanceBST(TreeNode root) {
        dfsTree(root);
        return getTree(res,0,res.size()-1);
    }


    public TreeNode getTree(List<Integer> list,int left,int right){
        if (left>right) return null;
        int mid=left+(right-left)/2;
        TreeNode root=new TreeNode(list.get(mid));
        root.left=getTree(list,left,mid-1);
        root.right=getTree(list,mid+1,right);
        return root;
    }


    public void dfsTree(TreeNode root){
        if (root==null) return;
        dfsTree(root.left);
        res.add(root.val);
        dfsTree(root.right);
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

}
